//
// Created by pangy on 2025/5/10.
//
// 顺序表实现

#include "SqList.h"

/**
 * 初始化
 * @param L
 * @return OK/ERROR
 */
Status InitList(SqList * L) {
    // 初始化分配表空间
    (*L).elem = (ElemType*) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if ((*L).elem == NULL) {
        // 存储空间分配失败
        exit(OVERFLOW);
    }
    (*L).length = 0;                        // 表长0
    (*L).listSize = LIST_INIT_SIZE;         // 初始化分配空间

    return OK;
}

/**
 * 销毁(结构)
 * 释放内存
 * @param L
 * @return OK/ERROR
 */
Status DestroyList(SqList* L) {
    // 确保线性表L存在
    if (L == NULL || (*L).elem == NULL) {
        return ERROR;
    }

    // 释放内存
    free((*L).elem);
    // 指针置空
    (*L).elem = NULL;
    // 表长度/容量置零
    (*L).length = 0;
    (*L).listSize = 0;

    return OK;
}

/**
 * 置空(内容)
 * 只置零长度, 不释放内存
 * @param L
 * @return
 */
Status ClearList(SqList* L) {
    // 确保线性表L存在
    if (L == NULL || (*L).elem == NULL) {
        return ERROR;
    }
    // 只将长度置零
    (*L).length = 0;

    return OK;
}

/**
 * 判空
 * 空表返回TRUE, 否则返回FALSE
 * */
Boolean ListEmpty(SqList L) {
    return L.length == 0 ? TRUE : FALSE;
}

/**
 * 长度
 * 返回线性表长度, 空表返回0
 * */
int ListLength(SqList L) {
    return L.length;
}

/**
 * 取值
 * 获取线性表指定位置的数据元素
 * @param L 线性表
 * @param i 索引
 * @param e 接收数据元素
 * @return OK/ERROR
 */
Status GetElem(SqList L, int i, ElemType* e) {
    // 索引i在范围[1, L.length]内
    if (i < 1 || i > L.length) {
        return ERROR;
    }

    *e = L.elem[i - 1];

    return OK;
}

/**
 * 查找
 * 查找指定元素位置
 * @param L 线性表
 * @param e 查找元素
 * @param Compare 比较函数
 * @return 与e匹配的数据元素的位置, 未找到返回0
 */
int LocateElem(SqList L, ElemType e, Status (*Compare)(ElemType, ElemType)) {
    // 确定线性表L存在
    if (L.elem == NULL) {
        return ERROR;
    }

    for (int i = 1; i <= L.length; ++i) {
        // 遍历线性表数据元素,调用函数Compare()进行比较,返回TRUE匹配
        if (Compare(L.elem[i-1], e)) {
            return i;
        }
    }

    return 0;
}

/**
 * 获取指定元素前驱
 * @param L 线性表
 * @param cur_e 指定数据元素
 * @param pre_e 前驱
 * @return OK/ERROR
 */
Status PriorElem(SqList L, ElemType cur_e, ElemType* pre_e) {
    // 确保线性表L存在,且至少有两个元素
    if (L.elem == NULL || L.length < 2) {
        return ERROR;
    }

    // 遍历线性表L,与指定数据元素比较
    int i = 0;
    while (i < L.length && L.elem[i] != cur_e) {
        i++;
    }

    // 第一个数据元素(没有前驱)匹配,或者没有匹配数据元素
    if (i == 0 || i >= L.length) {
        return ERROR;
    }

    *pre_e = L.elem[i - 1];

    return OK;
}

/**
 * 获取指定元素后继
 * @param L 线性表
 * @param cur_e 指定数据元素
 * @param next_e 后继
 * @return OK/ERROR
 */
Status NextElem(SqList L, ElemType cur_e, ElemType* next_e) {
    // 线性表L存在,且至少有两个数据元素
    if (L.elem == NULL || L.length < 2) {
        return ERROR;
    }

    int i = 0;
    while (i < L.length && L.elem[i] != cur_e) {
        i++;
    }

    // 匹配最后一个数据元素(没有后继),或者未匹配到数据元素, 返回ERROR
    if (i >= L.length - 1) {
        return ERROR;
    }

    *next_e = L.elem[i + 1];

    return OK;
}

/**
 * 在指定位置之前插入数据元素
 * @param L 线性表
 * @param i 指定位置
 * @param e 插入数据元素
 * @return OK/ERROR
 */
Status ListInsert(SqList* L, int i, ElemType e) {
    ElemType* newBase;
    ElemType *p, *q;

    // i值范围[1, L.length+1]
    if (i < 1 || i > L->length + 1) {
        return ERROR;
    }

    // 容量已满
    if (L->length > L->listSize) {
        // 分配新内存
        newBase = (ElemType*) realloc(L->elem, (L->listSize + LIST_INCREMENT) * sizeof (ElemType));
        if (!newBase) {
            exit(OVERFLOW);
        }
        L->elem = newBase;
        L->listSize += LIST_INCREMENT;
    }

    // 插入位置数据元素
    q = &L->elem[i - 1];
    // 表尾数据元素
    p = &L->elem[L->length - 1];

    // 移动i到表尾的数据元素
    for (; p >= q; --p) {
        *(p + 1) = *p;
    }

    // 赋值
    *q = e;

    // 表长加1
    L->length += 1;

    return OK;
}

/**
 * 删除指定位置的数据元素
 * @param L 线性表
 * @param i 位置
 * @param e 删除的数据元素
 * @return OK/ERROR
 */
Status ListDelete(SqList* L, int i, ElemType* e) {
    ElemType *p, *q;

    // i范围 [1, L.length]
    if (i < 1 || i > L->length) {
        return ERROR;
    }

    // p为删除数据元素位置
    p = &L->elem[i - 1];

    *e = *p;

    // 表尾数据元素位置
    q = &L->elem[L->length - 1];

    while (p < q) {
        *p = *(p + 1);
        ++p;
    }

    // 表长度减一
    L->length--;

    return OK;
}

/**
 * 线性表数据元素依次操作
 * @param L 线性表
 * @param Visit 操作函数
 * @return OK/ERROR
 */
void ListTraverse(SqList L, void (*Visit)(ElemType)) {
    for (int i = 0; i < L.length; ++i) {
        Visit(L.elem[i]);
    }
    printf("\n");
}

